

package insiemi;
import java.util.*;


// ATTENZIONE: nel seguito per i metodi da scrivere sara' indicato solo il
// prototipo, eventuali altre parole chiave (public, throws, implements, etc)
// le dovete mettere voi.


// Si consideri l'interfaccia:

interface ConDistanza {
    double distanza(Object a);
}


/* Si ricorda che questa dichiarazione dice semplicemente che per implementare
 * questa interfaccia una classe deve semplicemente
 * contenere il metodo distanza che fornisce una "distanza" fra this e un qualsiasi
 * altro oggetto. Il tipo di distanza da restituire verra' specificato
 * piu' avanti per le singole classi. */


/* si definisca una classe Punto che rappresenti un punto del piano cartesiano;
 * le variabili di istanza devono quindi contenere le coordinate x e y
 * del punto (usare dei double per rappresentare le coordinate).
 * La classe Punto deve implementare l'interfaccia ConDistanza e
 * contenere (almeno) i seguenti metodi: */


class Punto implements ConDistanza {
    double x1,y1;

    // Costruttore: Punto(double x, double y)
    // costruisce un punto con coordinate x e y

    Punto(double x, double y){
        x1=x;
        y1=y;
    }

    // boolean equals(Object obj)
    // restituisce true se e solo se obj appartiene alla classe Punto
    // (o sottoclasse) e ha le stesse coordinate di this

    public boolean equals(Object obj){
        if (obj instanceof Punto ) {
        Punto z=(Punto) obj;
        return x1==(z.x1) && y1==(z.y1);
        }
     return false;
    }
    // String toString()
    // restituisce una stringa contenente le coordinate del punto racchiuse tra
    // parentesi quadre
    @Override
    public String toString(){
        return "[" + x1 +","+ y1 + "]";
    }
    // double distanza(Object obj)
    // restituisce la distanza tra this e un qualsiasi altro oggetto obj secondo
    // la seguente formula: se obj non appartiene alla classe Punto (o sottoclasse)
    // la distanza e' 999999999 (e' come dire +infinito), altrimenti la distanza
    // da restituire e' la distanza euclidea fra this e obj (per calcolare
    // la radice quadrata usare Math.sqrt())

    public double distanza(Object obj){
        double ris;
        if (obj instanceof Punto ) {
            Punto q=(Punto) obj;
            ris=Math.pow((x1-q.x1),2)+Math.pow((y1-q.y1),2);
            return Math.sqrt(ris);
        }
      return   999999999;
    }
}



// Si definisca la classe Insieme che rappresenta un insieme di
// oggetti del tipo ConDistanza, cioe' di oggetti appartenenti a
// classi che implementano l'interfaccia ConDistanza

    class Insieme{
        List<ConDistanza> ins;
        List<Insieme> ins1;
// La classe Insieme deve quindi contenere una variabile d'istanza
// del tipo  List<ConDistanza> che permette di contenere
// una collezione di oggetti di tipo ConDistanza.

// Inoltre Insieme deve contenere i seguenti metodi:

    // costruttore: Insieme()
    // costruisce un insieme inizialmente vuoto

        Insieme(){
        ins=new ArrayList<ConDistanza>();
        }
    // boolean aggiungi(ConDistanza x)
    // aggiunge l'oggetto x all'insieme, ma solo se l'insieme
    // non contiene gia' un oggetto uguale (nel senso di equals) a x.
    // restituisce true se x viene aggiunto, false altrimenti
        public boolean aggiungi(ConDistanza x){
            if(ins.contains(x)) return false;
            ins.add(x);
            return true;
        }
    // int size()
    // restituisce il numero di oggetti attualmente dentro l'insieme

        public int size(){
            return ins.size();
        }
    // String toString()
    // restituisce una stringa contenente l'elenco degli oggetti
    // dell'insieme (tutti sulla stessa riga)
    // i singoli oggetti devono essere rappresentati con il relativo toString

    @Override
    public String toString(){
        String s="";
        for (ConDistanza i:ins){
            s+= i ;
        }
        return s;
}
    // double distanza_minima(Object x)
    // restituisce la minima distanza tra gli oggetti in this e l'oggetto  x
    // la distanza deve essere calcolata mediante il metodo distanza che e'
    // sicuramente definito per tutti gli oggetti nell'insieme this.
    // Se this e' vuoto restituisce 999999999 (come dire +infinito)
    // Notare che 999999999 puo' essere restituto anche se l'insieme non e'
    // vuoto (ad esempio se x non e' dello stesso tipo di nessuno degli
    // oggetti dell'insieme)

        public double distanza_minima(Object x){
        double min=999999999,temp;
        for (ConDistanza i:ins){
            temp= i.distanza(x);
            if (temp<min){
                    min=temp;
            }
        }
         return min;
        }




    // List<Insieme> dividi()
    // Divide gli elementi dell'insieme in due nuovi insiemi
    // (senza modificare l'insieme di partenza). Restituisce una lista di
    // due elementi contenente i due nuovi insiemi (uno o entrambi di questi
    // insiemi restituiti puo' essere vuoto)
    // La divisione degli elementi dell'insieme deve essere fatta sulla
    // base della loro distanza con il seguente procedimento:
    //  1. Se l'insieme di partenza e' vuoto restituisce 2 insiemi vuoti
    //  2. Se l'insieme di partenza contiene un solo elemento
    //     restituisce un insieme con un elemento e l'altro insieme vuoto
    //  3. Se l'insieme di partenza contiene almeno due elementi:
    //  3a.  considera la distanza tra tutte le coppie di elementi e seleziona
    //       la coppia di elementi che sono a distanza massima.
    //  3b.  mette il primo elemento della coppia nel primo insieme
    //       e il secondo elemento nel secondo insieme
    //  3c.  considera in successione tutti gli altri elementi dell'insieme
    //       di partenza: ogni elemento viene messo in quello dei due nuovi insiemi
    //       a cui l'elemento e' piu' vicino (per calcolare la distanza di un
    //       elemento da un insieme si usi il metodo distanza_minima)
   
        public List<Insieme> dividi(){
        double max=0;
        ConDistanza p1=null,p2=null;
        ins1=new ArrayList<Insieme>();
        ins1.add(0,new Insieme());
        ins1.add(1,new Insieme());
        if (ins.isEmpty()){
           
            return ins1;}
        if (ins.size() == 1){
          ins1.get(0).aggiungi(ins.get(0));
          return ins1;
        }
        for (ConDistanza i:ins){
            for (ConDistanza y:ins){
            if (i.distanza(y)>max){
                max=i.distanza(y);
                p1=i;p2=y;
             }
        }}

        for (ConDistanza x:ins){
            if (x.distanza(p1)<x.distanza(p2)){
                ins1.get(0).aggiungi(x);
            }
            else{
                 ins1.get(1).aggiungi(x);
            }
            
        }
        return ins1;
        }

}
    



/* --------- fine della prima parte dell'esercizio Java --------
 * Dato che per ottenere la sufficienza e' necessario scrivere anche codice
 * in Ruby vi consiglio di valutare quanto tempo e' rimasto e decidere
 * se iniziare con Ruby o affrontare la seconda parte dell'esercizio Java
 */


// Si definisca la classe Stringa che implementi l'interfaccia ConDistanza.
// Ogni oggetto della classe Stringa rappresenta semplicemente una stringa di testo
// La classe dovra' quindi avere una variabile d'istanza di tipo String che conterra'
// la stringa associata ad ogni istanza. Dobbiamo definire
// la classe Stringa invece di utilizzare semplicemente la classe String perche'
// vogliamo una classe che implementi l'interfaccia ConDistanza e quindi contenga
// il metodo distanza() che ovviamente in String non e' definito.

// La classe Stringa deve contenere almeno i seguenti metodi:
   

    class Stringa extends Insieme implements ConDistanza{
    String q;

    // Costruttore: Stringa(String z)
    // costruisce un oggetto Stringa associandogli la stringa z

        Stringa(String z){
            q=z;
        }
    // boolean equals(Object obj)
    // restituisce true se e solo se obj appartiene alla classe Stringa
    // (o sottoclasse) e contiene la stessa stringa di this

    @Override
          public boolean equals(Object obj){
              if (obj instanceof Stringa){
                Stringa w=(Stringa) obj;
                return w.equals(q);
              }
              else {
                  return false;
              }
        }

   


    // String toString()
    // restituisce la stringa associata a this
    @Override
    public String toString(){
           return q;
    }


    // double distanza(Object o)
    // restituisce la distanza tra this e un qualsiasi altro oggetto obj secondo
    // la seguente formula: se obj non appartiene alla classe Stringa (o sottoclasse)
    // la distanza e' 999999999 (come dire +infinito), altrimenti la distanza
    // da restituire e' data dalla sequente formula. Sia s1 la stringa associata
    // a this e s2 la stringa associata a obj. La distanza e' data dalla somma
    // tra il numero di caratteri di s1 che non appaiono in s2 + il numero di
    // caratteri in s2 che non appaiono in s1. Esempi:
    //   distanza(sale,sole) = 2     ("a" + "o")
    //   distanza(sale,ssoole) = 3   ("a" + 2 "o")
    //   distanza(a,bbbbaa) = 4      (4 "b")
    //   distanza(bbbbaa,"") = 6     (4 "b" + 2 "a")
    // Importante: per calcolare questa distanza sono utili i metodi
    //             charAt() e indexOf() della classe String.
    public double distanza(Object o){
        int i,cont=0;
        if (o instanceof Stringa){
           String a=(String) o;
            for (i=0;1<q.length();i++){
             if (a.indexOf((q.charAt(i)))==-1){
                 cont++;
             }
             if (q.indexOf((a.charAt(i)))==-1){
                 cont++;
             }
            }
            return cont;
        }
        else {
            return 999999999;
        }
    }
}
/* A questo punto dovete riscrivere tutto in Ruby. Ricordo che in Ruby
 * il concetto di interfaccia non esiste, quindi limitatevi a scrivere
 * le 3 classi Punto Insieme e Stringa in modo che al momento dell'esecuzione
 * si comportino come le corrispondenti classi Java. */


/* Per verificare la correttezza del vostro codice Java potete utilizzare
 * il metodo main della classe insieme che dovrebbe produrre un output simile
 * a quello riportato in fondo a questo file. */

/* Per verificare la correttezza del costro codice Ruby potete utilizzare
   il metodo main() riportato piu' avanti che dovrebbe produrre anch'esso
   lo stesso output */


class Main {

    public static void main(String[] args) {

      Insieme punti, stringhe, misto;

      System.out.println("============== inizio test =========");
      punti = new Insieme();
      stringhe = new Insieme();
      misto = new Insieme();
      System.out.println("-------- inserimento punti ---------");
      punti.aggiungi(new Punto(3,4));
      punti.aggiungi(new Punto(0,-1));
      punti.aggiungi(new Punto(3,4));
      System.out.println(punti.size());
      punti.aggiungi(new Punto(2,4));
      punti.aggiungi(new Punto(-1,-10));
      punti.aggiungi(new Punto(3,4));
      punti.aggiungi(new Punto(33,4));
      punti.aggiungi(new Punto(-2,-1));
      punti.aggiungi(new Punto(2,4));
      System.out.println(punti.size());
      System.out.println("-------- contenuto insieme ---------\n" + punti);

      System.out.println("-------- distanza minima ---------");
      System.out.println(punti.distanza_minima(new Punto(0,0)));
      System.out.println(punti.distanza_minima(new Punto(10,0)));
      System.out.println(punti.distanza_minima(new Punto(10,10)));
      System.out.println(punti.distanza_minima(new Punto(2,4)));
      System.out.println(punti.distanza_minima("Ciao"));
      System.out.println(punti.distanza_minima(7));
      System.out.println(misto.distanza_minima(new Punto(0,0)));

      System.out.println("-------- dividi ---------");
      List<Insieme> parti;
      parti = misto.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      misto.aggiungi(new Punto(3,3));
      parti = misto.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      misto.aggiungi(new Punto(30,30));
      parti = misto.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      parti = punti.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      punti.aggiungi(new Punto(30,-1));
      parti = punti.dividi();
      punti.aggiungi(new Punto(26,4));
      parti = punti.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      System.out.println("-------- le 2 parti ---------");
      System.out.println(parti.get(0)+"\n--\n"+ parti.get(1));

      System.out.println("==== inizio test del tipo Stringa ====");
      System.out.println("-------- prove distanze stringhe ---------");
      System.out.println((new Stringa("sale")).distanza(new Stringa("sole")));
      System.out.println((new Stringa("sale")).distanza(new Stringa("la")));
      System.out.println((new Stringa("sale")).distanza(new Stringa("alealeale")));
      System.out.println((new Stringa("alealeale")).distanza(new Stringa("sale")));
      System.out.println((new Stringa("zorro")).distanza(new Stringa("")));

      System.out.println("-------- inserimento stringhe ---------");
      stringhe.aggiungi(new Stringa("sale"));
      stringhe.aggiungi(new Stringa("mare"));
      stringhe.aggiungi(new Stringa("mare"));
      System.out.println(stringhe.size());
      stringhe.aggiungi(new Stringa("torino"));
      stringhe.aggiungi(new Stringa("tondino"));
      stringhe.aggiungi(new Stringa("sole"));
      stringhe.aggiungi(new Stringa("rito"));
      stringhe.aggiungi(new Stringa("sole"));
      stringhe.aggiungi(new Stringa("vela"));
      System.out.println(stringhe.size());
      System.out.println("-------- contenuto insieme ---------\n" + stringhe);

      System.out.println("-------- distanza minima ---------");
      System.out.println(stringhe.distanza_minima(new Stringa("zio")));
      System.out.println(stringhe.distanza_minima(new Stringa("")));
      System.out.println(stringhe.distanza_minima(new Stringa("scatole")));
      System.out.println(stringhe.distanza_minima(new Stringa("oop")));
      System.out.println(stringhe.distanza_minima(new Stringa("Ciao")));
      System.out.println(stringhe.distanza_minima(7));
      System.out.println(stringhe.distanza_minima(new Punto(2,3)));

      System.out.println("-------- dividi stringhe ---------");
      parti = stringhe.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      System.out.println("-------- le 2 parti ---------");
      System.out.println(parti.get(0)+"\n--\n"+ parti.get(1));
      System.out.println("-------- dividi misto ---------");
      misto.aggiungi(new Stringa("java"));
      misto.aggiungi(new Stringa("ruby"));
      misto.aggiungi(new Punto(4,2));
      System.out.println(misto);
      parti = misto.dividi();
      System.out.println(parti.get(0).size()+" "+ parti.get(1).size());
      System.out.println("-------- le 2 parti ---------");
      System.out.println(parti.get(0)+"\n--\n"+ parti.get(1));

      System.out.println("================ fine test ===========");
    }

        }


/* #####  main ruby #######


def main

      puts "============== inizio test ========="

      punti = Insieme.new
      stringhe = Insieme.new
      misto = Insieme.new
      puts "-------- inserimento punti ---------"

      punti.aggiungi(Punto.new(3,4))
      punti.aggiungi(Punto.new(0,-1))
      punti.aggiungi(Punto.new(3,4))
      puts punti.size()
      punti.aggiungi(Punto.new(2,4))
      punti.aggiungi(Punto.new(-1,-10))
      punti.aggiungi(Punto.new(3,4))
      punti.aggiungi(Punto.new(33,4))
      punti.aggiungi(Punto.new(-2,-1))
      punti.aggiungi(Punto.new(2,4))
      puts punti.size()

      puts "-------- contenuto insieme ---------\n#{punti}"

      puts "-------- distanza minima ---------"
      puts punti.distanza_minima(Punto.new(0,0))
      puts punti.distanza_minima(Punto.new(10,0))
      puts punti.distanza_minima(Punto.new(10,10))
      puts punti.distanza_minima(Punto.new(2,4))
      puts punti.distanza_minima("Ciao")
      puts punti.distanza_minima(7)
      puts misto.distanza_minima(Punto.new(0,0))

      puts "-------- dividi ---------"
      parti = misto.dividi()
      puts "#{parti[0].size()} #{parti[1].size()}"
      misto.aggiungi(Punto.new(3,3))
      parti = misto.dividi()
      puts "#{parti[0].size()} #{parti[1].size()}"
      misto.aggiungi(Punto.new(30,30))
      parti = misto.dividi()
      puts "#{parti[0].size()} #{parti[1].size()}"
      parti = punti.dividi()
      puts "#{parti[0].size()} #{parti[1].size()}"
      punti.aggiungi(Punto.new(30,-1))
      parti = punti.dividi()
      punti.aggiungi(Punto.new(26,4))
      parti = punti.dividi()
      puts "#{parti[0].size()} #{parti[1].size()}"
      puts "-------- le 2 parti ---------"
      puts "#{parti[0]}\n--\n#{parti[1]}"

      puts "==== inizio test del tipo Stringa ===="
      puts "-------- prove distanze stringhe ---------"
      puts (Stringa.new("sale")).distanza(Stringa.new("sole"))
      puts (Stringa.new("sale")).distanza(Stringa.new("la"))
      puts (Stringa.new("sale")).distanza(Stringa.new("alealeale"))
      puts (Stringa.new("alealeale")).distanza(Stringa.new("sale"))
      puts (Stringa.new("zorro")).distanza(Stringa.new(""))

      puts "-------- inserimento stringhe ---------"
      stringhe.aggiungi(Stringa.new("sale"))
      stringhe.aggiungi(Stringa.new("mare"))
      stringhe.aggiungi(Stringa.new("mare"))
      puts stringhe.size()
      stringhe.aggiungi(Stringa.new("torino"))
      stringhe.aggiungi(Stringa.new("tondino"))
      stringhe.aggiungi(Stringa.new("sole"))
      stringhe.aggiungi(Stringa.new("rito"))
      stringhe.aggiungi(Stringa.new("sole"))
      stringhe.aggiungi(Stringa.new("vela"))
      puts stringhe.size()
      puts "-------- contenuto insieme ---------\n#{stringhe}"

      puts "-------- distanza minima ---------"
      puts stringhe.distanza_minima(Stringa.new("zio"))
      puts stringhe.distanza_minima(Stringa.new(""))
      puts stringhe.distanza_minima(Stringa.new("scatole"))
      puts stringhe.distanza_minima(Stringa.new("oop"))
      puts stringhe.distanza_minima("Ciao")
      puts stringhe.distanza_minima(7)
      puts stringhe.distanza_minima(Punto.new(2,3))

      puts "-------- dividi stringhe ---------"
      parti = stringhe.dividi()
      puts "#{parti[0].size} #{parti[1].size}"
      puts "-------- le 2 parti ---------"
      puts "#{parti[0]}\n--\n#{parti[1]}"
      puts "-------- dividi misto ---------"
      misto.aggiungi(Stringa.new("java"))
      misto.aggiungi(Stringa.new("ruby"))
      misto.aggiungi(Punto.new(4,2))
      puts misto
      parti = misto.dividi()
      puts "#{parti[0].size} #{parti[1].size}"
      puts "-------- le 2 parti ---------"
      puts "#{parti[0]}\n--\n#{parti[1]}"

      puts "================ fine test ==========="

end


   ##### fine main ruby ###### */

/*

============== inizio test =========
-------- inserimento punti ---------
2
6
-------- contenuto insieme ---------
[3.0,4.0] [0.0,-1.0] [2.0,4.0] [-1.0,-10.0] [33.0,4.0] [-2.0,-1.0]
-------- distanza minima ---------
1.0
8.06225774829855
9.219544457292887
0.0
9.99999999E8
9.99999999E8
9.99999999E8
-------- dividi ---------
0 0
1 0
1 1
5 1
5 3
-------- le 2 parti ---------
[-1.0,-10.0] [3.0,4.0] [0.0,-1.0] [2.0,4.0] [-2.0,-1.0]
--
[33.0,4.0] [30.0,-1.0] [26.0,4.0]
==== inizio test del tipo Stringa ====
-------- prove distanze stringhe ---------
2.0
2.0
1.0
1.0
5.0
-------- inserimento stringhe ---------
2
7
-------- contenuto insieme ---------
sale mare torino tondino sole rito vela
-------- distanza minima ---------
3.0
4.0
3.0
4.0
9.99999999E8
9.99999999E8
9.99999999E8
-------- dividi stringhe ---------
4 3
-------- le 2 parti ---------
sale mare sole vela
--
tondino torino rito
-------- dividi misto ---------
[3.0,3.0] [30.0,30.0] java ruby [4.0,2.0]
3 2
-------- le 2 parti ---------
[3.0,3.0] [30.0,30.0] [4.0,2.0]
--
java ruby
================ fine test ===========


*/